package pr2012.practico5.sort;

public class TClasificador {
    public static final int METODO_CLASIFICACION_BURBUJA = 1;
    public static final int METODO_CLASIFICACION_SELECCION_DIRECTA = 2;
	public static final int METODO_CLASIFICACION_INSERCION_DIRECTA = 3;
    public static final int METODO_CLASIFICACION_SHELLSORT = 4;
    public static final int METODO_CLASIFICACION_QUICKSORT = 5;
    public static final int METODO_CLASIFICACION_HEAPSORT = 6;
    
    public int[] clasificar(int[] datosParaClasificar, int metodoClasificacion){
            switch (metodoClasificacion) {
                    case METODO_CLASIFICACION_INSERCION_DIRECTA:
                            return ordenarPorInsercion(datosParaClasificar);
                    case METODO_CLASIFICACION_SHELLSORT:
                            return ordenarPorShellSort(datosParaClasificar);
                    case METODO_CLASIFICACION_BURBUJA:
                            return ordenarPorBurbuja(datosParaClasificar);
                    case METODO_CLASIFICACION_QUICKSORT:
                            return ordenarPorQuickSort(datosParaClasificar);
                    case METODO_CLASIFICACION_SELECCION_DIRECTA:
                            return ordenarPorSeleccionDirecta(datosParaClasificar);
                    case METODO_CLASIFICACION_HEAPSORT:
                            return ordenarPorHeapSort(datosParaClasificar);
                    default:
                            System.err.println("Este codigo no deberia haberse ejecutado");
                            return null;
            }
    }
    
    protected int[] ordenarPorShellSort(int[] datosParaClasificar){
            int j, inc;
            int[] incrementos = new int[] {3223, 350, 51, 10, 3, 1};
            
            for (int posIncrActual = 0; posIncrActual < incrementos.length; posIncrActual++){
                    inc = incrementos[posIncrActual];
                    if (inc < (datosParaClasificar.length)/2){
                            for (int i = inc; i < datosParaClasificar.length; i++){
                                    j = i - inc;
                                    while (j>=0){
                                            if (datosParaClasificar[j]>datosParaClasificar[j + inc]){
                                                    intercambiar(datosParaClasificar, j, j + inc);
                                                    j--;
                                            }
                                            else{
                                                    break;
                                            }
                                    }
                            }
                    }
            }
            return datosParaClasificar;
    }
    
    protected void intercambiar(int[] vector, int pos1, int pos2) {
            int aux;
            aux = vector[pos1];
            vector[pos1] = vector[pos2];
            vector[pos2] = aux;
    }

    protected int [] ordenarPorInsercion(int[] datosParaClasificar){
        if(datosParaClasificar != null ){
                  for(int i=1; i < datosParaClasificar.length; i++){
                     int j = i-1;
                     while((j>=0) && (datosParaClasificar[j] > datosParaClasificar[j+1])){
                             intercambiar(datosParaClasificar, j, j+1);
                             j--;
                     }
                  }
                  return datosParaClasificar;
            }
            return null;
    }

    public void imprimirVector(int [] vector, int comienzo, int fin){
            int posicionActual = comienzo;
            while(posicionActual<=fin){
                    System.out.print(vector[posicionActual]+" ");
                posicionActual++;
            }
                System.out.println(" ");
    }
    
    /**
     * @param datosParaClasificar
     * @return
     */
    protected int[] ordenarPorBurbuja(int[] datosParaClasificar){
            for (int i=0; i<=datosParaClasificar.length-1; i++){
                    for (int j=datosParaClasificar.length-1; j>=i+1; j--){
                            if (datosParaClasificar[j]<datosParaClasificar[j-1]){
                                    intercambiar(datosParaClasificar, j, j-1);
                            }
                    }
            }
            return datosParaClasificar;
    }
    
    protected int[] ordenarPorQuickSort(int[] datosParaClasificar){
            quickSort(datosParaClasificar, 0, datosParaClasificar.length-1);
            return datosParaClasificar;
    }
    
    private void quickSort(int[] datosParaClasificar, int i, int j){
            int izquierda = i;
            int derecha = j;
            int posPivote = encuentraPivote(izquierda, derecha, datosParaClasificar);
            if (posPivote >= 0){
                    int pivote = datosParaClasificar[posPivote];
                    while (izquierda <= derecha){
                            while ((datosParaClasificar[izquierda] < pivote)&&(izquierda < j)){
                                    izquierda ++;
                            }
                            while ((pivote < datosParaClasificar[derecha])&&(derecha > i)){
                                    derecha --;
                            }
                            if (izquierda <= derecha){
                                    intercambiar(datosParaClasificar, izquierda, derecha);
                                    izquierda ++;
                                    derecha --;
                            }
                    }
                    if (i < derecha){
                            quickSort(datosParaClasificar, i, derecha);
                    }
                    if (izquierda < j){
                            quickSort(datosParaClasificar, izquierda, j);
                    }
            }
    }
    
    private int encuentraPivote(int l,int r,int[]entrada){
            if (l < r){                     
                    int medio = (l + r) / 2;
                    if (entrada[l] < entrada[r]){
                            if (entrada[l] > entrada[medio]){
                                    return l;
                            } else {
                                    if (entrada[medio] < entrada[r]){
                                            return medio;
                                    } else {                                                
                                            return r;
                                    }
                            }
                    } else {
                            if (entrada[l] > entrada[r]){
                                    if (entrada[l] < entrada[medio]){
                                            return l;
                                    } else {
                                            if (entrada[r] < entrada[medio]){
                                                    return medio;
                                            } else {                                                        
                                                    return r;
                                            }
                                    }                                       
                            } else {
                                    int aux = entrada[l];
                                    for(int k = l+1; k < r; k++){
                                            if(entrada[k]!= aux){
                                                    if(entrada[k] > aux)
                                                            return k;
                                                    else
                                                            return l;
                                            }
                                    }
                                    return -1;
                            }
                    }
            } else {
                    return -1;
            }
    }
    
    protected int[] ordenarPorSeleccionDirecta(int[] datosParaClasificar){
            for (int i=0; i<=datosParaClasificar.length-1; i++){
                    int menor = datosParaClasificar[i];
                    int indiceMenor = i;
                    for (int j=i+1; j<datosParaClasificar.length; j++){
                            if (datosParaClasificar[j]<menor){
                                    menor = datosParaClasificar[j];
                                    indiceMenor = j;
                            }
                    }
                    intercambiar(datosParaClasificar, i, indiceMenor);
            }
            return datosParaClasificar;
    }
    
    protected int[] ordenarPorHeapSort(int[] datosParaClasificar){
            for (int i = (datosParaClasificar.length - 1) / 2; i >= 0; i--){
                    armaHeap(datosParaClasificar, i, datosParaClasificar.length - 1);
            }
            for (int i = datosParaClasificar.length - 1; i >= 1; i--){
                    intercambiar(datosParaClasificar,0,i);
                    armaHeap(datosParaClasificar, 0, i-1);
            }
            return datosParaClasificar;
    }
    
    private void armaHeap(int[] datosParaClasificar, int primero, int ultimo){
            if (primero < ultimo){
                    int r = primero;
                    while(r <= ultimo / 2){
                            if (ultimo == 2*r){ //r tiene un hijo solo
                                    if (datosParaClasificar[r] < datosParaClasificar[r*2]){
                                            intercambiar(datosParaClasificar, r, 2 * r);
                                            r = 2 * r;
                                    } else
                                            r = ultimo;
                            } else { //r tiene 2 hijos
                                    int posicionIntercambio = 0;
                                    if (datosParaClasificar[2*r] > datosParaClasificar[2*r + 1]){
                                            posicionIntercambio = 2 * r;
                                    } else
                                            posicionIntercambio = 2 * r + 1;
                                    if (datosParaClasificar[r] < datosParaClasificar[posicionIntercambio]){
                                            intercambiar(datosParaClasificar,r,posicionIntercambio);
                                            r = posicionIntercambio;
                                    } else
                                            r = ultimo;
                            }
                    }
            }
    }

}

